import java.util.PriorityQueue;

public class Solution {
    public ListNode mergeKLists1(ListNode[] lists) {
        int len = lists.length;
        if (len == 1) {
            return lists[0];
        } else if (len == 0) {
            return null;
        }
        int count = 1;
        ListNode head = lists[0];
        while (count < len) {
            head = method(head, lists[count++]);
        }
        return head;
    }

    public ListNode method(ListNode list1, ListNode list2) {//合并两个有序链表
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode head = new ListNode();
        ListNode cur = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
            } else if (cur1.val > cur2.val) {
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
            } else {
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
            }
        }
        if (cur1 == null) {
            cur.next = cur2;
        }
        if (cur2 == null) {
            cur.next = cur1;
        }
        return head.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> (v1.val - v2.val));//优先级队列，小根堆
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }
        ListNode ret = new ListNode();
        ListNode cur = ret;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                heap.offer(node.next);
            }
        }
        return ret.next;
    }
}
